◀ Prev · Parts · Full · Next ▶

A linear program with no integrality constraints can be solved in time polynomial in the number of variables and constraints. The problem is that the number of variables in the fractional configuration LP is equal to the number of possible configurations, which might be huge. Karmarkar and Karpcite-ref-12-9-0[9] present an algorithm that overcomes this problem.

First, they construct the dual linear program of the fractional LP:

maximize n ⋅ ⋅ y {\displaystyle ~\mathbf {n} \cdot \mathbf {y} ~} s.t. A T y ≤ ≤ 1 {\displaystyle ~A^{T}\mathbf {y} \leq \mathbf {1} ~} and y ≥ ≥ 0 {\displaystyle ~\mathbf {y} \geq 0} .

It has S variables y1,...,yS, and C constraints: for each configuration c, there is a constraint A c ⋅ ⋅ y ≤ ≤ 1 {\displaystyle A^{c}\cdot y\leq 1} , where A c {\displaystyle A^{c}} is the column of A representing the configuration c. 3It has the following economic interpretation.cite-ref-12-9-1[9] For each size s, we should determine a nonnegative price ys. Our profit is the total price of all items. We want to maximize the profit n y subject to the constraints that the total price of items in each configuration is at most 1.

◀ Prev · Parts · Full · Next ▶